Cryptography provides privacy and authentication for remote communications and data storage. Privacy may be provided by encrypting data using symmetric cryptography. Symmetric cryptography uses a single mathematical key to encrypt and decrypt data. However, symmetric cryptography, whose algorithms use the same key to encrypt and decrypt a message require the sharing of a secret for authentication. Authentication may be provided using the functions of user identification, data integrity, and message non-repudiation.
Asymmetric or public-key cryptography enables encrypted communication between users who have not previously established a shared secret key. Public-key cryptography is based on key pairs. A key pair consists of a private key and a public key. The private key is only known by its owner, while the public key is typically associated with its owner in an authenticated manner and shared with others. The public key is used to encrypt the message, and the private key is used to decrypt the message. As a result, the encrypted message may be sent using an insecure channel with the assurance that only the intended recipient can decrypt it. Public key encryption may be interactive (e.g., encrypting a telephone conversation) or non-interactive (e.g., encrypting electronic mail).
Identification protocols may be used to provide user identification. For example, digital signature may be used to provide data integrity, message non-repudiation, and user identification. A public key is used to encrypt or verify a signature of a message, and a private key is used to decrypt or generate a signature of a message.
U.S. Pat. No. 4,200,770, entitled “CRYPTOGRAPHIC APPARATUS AND METHOD,” describes the use of cryptographic key pairs and their application to the problem of key agreement over an insecure communication channel. The algorithms specified in U.S. Pat. No. 4,200,770 relies on the difficulty of the mathematical problem of finding a discrete logarithm for their security. U.S. Pat. No. 4,200,770 is hereby incorporated herein by reference in its entirety for all purposes.
Security of a discrete-logarithm based crypto algorithm may be undermined by performing the inverse of modular exponentiation (i.e., a discrete logarithm). Although mathematical methods for finding a discrete logarithm exist (e.g., the Number Field Sieve), these methods are hard to complete in a reasonable time period if certain conditions are met in the specification of the crypto algorithm, for example, if sufficiently large numbers are used. Large numbers require more time and computing power to find the discrete logarithm and break the cryptograph. However, large numbers result in long public keys and slow transmissions of cryptographic data. In addition, the use of very large numbers also requires longer processing times and greater computational power to perform the crypto algorithm. As a result, cryptographers continue to search for ways to minimize the size of the numbers used and the computational power required to perform the encryption and/or authentication algorithms.